class Solution:
    def __init__(self):
        self.bits = 0
        self.n = 0

    def findKthNumber(self, n: int, k: int) -> int:
        # 计算数字位数
        self.bits = len(str(n))
        self.n = n

        # 计算第一个数字
        ans = ""
        for j in range(1, 10):
            v = self.count(str(j))
            # print("第", 1, "位", ":", j, "=", v)
            if k > v:
                k -= v
            else:
                ans = str(j)
                break
        k -= 1
        if k == 0:
            return int(ans)

        # 计算其他数字
        for i in range(1, self.bits):
            for j in range(0, 10):
                prefix = ans + str(j)
                v = self.count(prefix)
                if k > v:
                    k -= v
                else:
                    ans += str(j)
                    break
            k -= 1
            if k == 0:
                return int(ans)

        return int(ans)

    def count(self, prefix: str):
        """前缀p有多少子结点"""
        size = len(prefix)

        bit = self.bits - size

        ans = 0
        for i in range(bit):
            ans += 10 ** i

        left = int(prefix) * (10 ** bit)
        right = (int(prefix) + 1) * (10 ** bit)

        # print("前缀:", prefix, "->", ans, "->", [left, right])

        if self.n < left:
            return ans
        elif left <= self.n < right:
            return ans + (self.n - left + 1)
        else:  # right <= self.n
            return ans + (right - left)


if __name__ == "__main__":
    print("[ANS]", Solution().findKthNumber(13, 2))  # 10

    # 自制用例
    print("[ANS]", Solution().findKthNumber(112, 2))  # 10
    print("[ANS]", Solution().findKthNumber(112, 24))  # 19

    # 测试用例29
    print("[ANS]", Solution().findKthNumber(2, 2))  # 2
